1744D - Divisibility by 2n - CodeForces Solution

/***********************************************************************************************************************
                                  <<<<<<<<<<<<<<<<<<<<<<♥♥♥♥♥♥صلي على النبي وتبسم ♥♥♥♥♥♥>>>>>>>>>>>>>>>>>>>
    **********************************************************************************************************************/
#include <iostream>
#include <iomanip>
#include <cmath>
#include <sstream>
#include <algorithm>
#include <string>
#include <vector>
#include <iterator>
#include <deque>
#include <queue>
#include <stack>
#include <utility>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <numeric>

using namespace std;
#define ll long long
#define ld long double
#define ull unsigned long long
#define endl '\n'
#define FAST ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define all(c) (c).begin(), (c).end()
#define rall(c) c.rbegin(), c.rend()
#define Sort(c) sort(all(c))
#define Reverse(c) reverse(all(c))
#define cin(c) for(auto&i:c)cin>>i;
#define cout(c) for(auto&i:c)cout<<i<<' '
#define cinpair(c) for(auto&i:c)cin>>i.first>>i.second
#define coutpair(c) for(auto&i:c)cout<<i.first<<' '<<i.second<<'\n'
#define sz(v) v.size()
#define F first
#define S second
#define pb push_back
#define fixed(n) fixed << setprecision(n)

bool IsPowerOf2(int x) {
    return (x && !(x & x - 1));
}

int computeXOR(int n) {
    if (n % 4 == 0)return n;
    if (n % 4 == 1)return 1;
    if (n % 4 == 2)return n + 1;
    else return 0;
}

int getFirstOneIdx(int n) {
    return log2(n & -n);
}

int getBit(int num, int idx) {
    return ((num >> idx) & 1) == 1;
}

int setBit1(int num, int idx) {
    return num | (1 << idx);
}

int setBit0(int num, int idx) {
    return num & ~(1 << idx);                // 110100, idx = 3  -->  110100 & ~000100 = 110100 & 111011
}

int flipBit(int num, int idx) {
    return num ^ (1 << idx);
}

int BinaryExponentiationREC(int a, int b) {
    if (!b)
        return 1;
    int ret = BinaryExponentiationREC(a, b / 2);
    return (b & 1 ? ret * ret * a : ret * ret);
}

ll BinaryExponentiation(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1)res *= a;
        a *= a;
        b /= 2;
    }
    return res;
}

ll ModularExponentiation(ll a, ll b, ll m) {
    ll res = 1;
    while (b) {
        if (b & 1)res = (res * a) % m;
        a = (a * a) % m;
        b /= 2;
    }
    return res;
}

ll gcd(ll a, ll b)  //O( log(max(a,b)) )
{
    //gcd (a,b)=gcd(b,a%b)
    // if b=0 stop
    while (b != 0) {
        ll a2 = a;
        a = b;
        b = a2 % b;
    }
    return a;
}

ll lcm(ll a, ll b) {
    //return ((a * b) / gcd(a, b));
    return (a / gcd(a, b)) * b;
}

ll Modulo(ll a, ll b) {
    return (((a % b) + b) % b);
}

int MOD=1000000007;

void solve() {
    int n;
    cin>>n;
    int a[n+1],temp[n+1];
    for(int i=1;i<=n;++i)cin>>a[i],temp[i]=a[i];
    int n2{},ans{};
    for(int i=1;i<=n;++i)
    {
        while(a[i]%2==0)
        {
            n2++;
            a[i]/=2;
        }
    }
    if(n2>=n)
    {
        cout<<0;
        return;
    }
    vector<int>ch;
    for(int i=1;i<=n;++i)
    {
        int nn{};
        int r=i;
        while(r%2==0)
        {
            nn++;
            r/=2;
        }
        ch.emplace_back(nn);
    }
    sort(rall(ch));
    for(int i=0;i<sz(ch);++i)
    {
        n2+=ch[i];
        ans++;
        if(n2>=n)
        {
            cout<<ans;
            return;
        }
    }
    cout<<-1;
}

int main() {
    FAST
    ll testcases = 1;
    cin >> testcases;
    while (testcases--) {
        solve();
        cout << endl;
    }
    return 0;
}